package algorithmic_data_structure.KMP算法;

import org.junit.Test;

/**
 * KMP算法的最大好处就是str1串是不需要回滚的
 */
public class 手写KMP {
    @Test
    public void test(){
        System.out.println(KMPMatch("lwlllwllllwlllwwwwwl", "llw"));
        System.out.println("lwlllwllllwlllwwwwwl".indexOf("llw"));
        System.out.println(KMPMatch("lwlllwllllwlllwwwwwl", "l"));
        System.out.println("lwlllwllllwlllwwwwwl".indexOf("l"));
        System.out.println(KMPMatch("lwlllwllllwlllwwwwwl", "llwwww"));
        System.out.println("lwlllwllllwlllwwwwwl".indexOf("llwwww"));
    }
    public static int KMPMatch(String s1,String s2){
        if (s2 == null || s2.length() == 0 || s1.length() < s2.length()){
            return -1;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        //next : 某一个位置算错了，应该跳到哪一个next？
        int[] next = getNextArray(str2);
        int i = 0,j = 0;
        while (i < str1.length && j < str2.length){
            if (str1[i] == str2[j]){
                i ++;
                j ++;
            }else if (next[j] == -1){
                i ++;   //next数组已经移动到第一位了，只能移动str1了
            }else{
                j = next[j];
            }
        }
        return j == str2.length ? i - j : -1;
    }

    private static int[] getNextArray(char[] str2) {
        if (str2.length == 1){
            return new int[]{-1};
        }
        int[] next = new int[str2.length];
        next[0] = -1;
        next[1] = 0;
        int beforeSame = 0;
        int j = 2;
        while (j < str2.length){
            if (str2[j-1] == str2[beforeSame]){
                next[j++] = ++beforeSame;
            }else if (next[beforeSame] == -1){
                next[j++] = 0;
            }else{
                beforeSame = next[beforeSame];
            }
        }
        return next;
    }
}
